package suanfa.skipList;


import java.util.Random;

public class SkipList {

    private static final double PROMOTE_RATE=0.5;

    private Node head,tail;

    private int maxLevel;

    public SkipList(){
        head=new Node(Integer.MIN_VALUE);
        tail=new Node(Integer.MAX_VALUE);

        head.right=tail;

        tail.left=head;

    }

    /**
     * 鏌ユ壘鑺傜偣
     * @return
     */
    public Node search(int data){
        Node p=findNode(data);

        if(p.data==data){
            System.out.println("鎵惧埌鑺傜偣锛�"+data);
            return p;
        }
        System.out.println("鏈壘鍒拌妭鐐癸細"+data);
        return null;
    }

    private Node findNode(int data){
        Node node=head;

        while(true){
            while (node.right.data !=Integer.MAX_VALUE && node.right.data<data){
                node=node.right;
            }
            if(node.down==null){
                break;
            }
            node=node.down;
        }
        return node;
    }


    public void insert(int data){
        Node preNode=findNode(data);

        //濡傛灉data鐩稿悓锛岀洿鎺ヨ繑鍥�
        if(preNode.data==data){
            return;
        }

        Node node=new Node(data);

        appendNode(preNode,node);

        int currentLevel=0;

        //闅忓嵆鍐冲畾鑺傜偣鏄惁鏅嬪崌
        Random random = new Random();

        while(random.nextDouble()<PROMOTE_RATE){
            if(currentLevel==maxLevel){
                addLevel();
            }

            while(preNode.up==null){
                preNode=preNode.left;
            }

            preNode=preNode.up;

            //鎶娾�濇檵鍗団�滅殑鏂拌妭鐐规彃鍒颁笂涓�灞�
            Node upperNode=new Node(data);

            appendNode(preNode,upperNode);

            upperNode.down=node;

            node.up=upperNode;

            node=upperNode;

            currentLevel++;

        }


    }

    private void appendNode(Node preNode,Node newNode){
        newNode.left=preNode;

        newNode.right=preNode.right;

        preNode.right.left=newNode;

        preNode.right=newNode;
    }


    private void addLevel(){
        maxLevel++;
        Node p1=new Node(Integer.MIN_VALUE);

        Node p2=new Node(Integer.MAX_VALUE);

        p1.right=p2;
        p2.left=p1;

        p1.down=head;

        head.up=p1;

        p2.down=tail;

        tail.up=p2;

        head=p1;
        tail=p2;
    }


    public boolean remove(int data){
        Node removeNode=search(data);

        if(removeNode==null){
            return false;
        }

        int currentLevel=0;

        while(removeNode!=null){
            removeNode.right.left=removeNode.left;

            removeNode.left.right=removeNode.right;

            if(currentLevel!=0 && removeNode.left.data==Integer.MIN_VALUE &&removeNode.right.data==Integer.MAX_VALUE){
                removeLevel(removeNode.left);
            }else{
                currentLevel++;
            }
            removeNode=removeNode.up;
        }
        return true;
    }

    private void removeLevel(Node leftNode){
        Node rightNode=leftNode.right;

        if(leftNode.up==null){
            leftNode.down=head;
            leftNode.down.up=null;
            rightNode.down.up=null;
        }
        else{
            leftNode.up.down=leftNode.down;

            leftNode.down.up=leftNode.up;

            rightNode.up.down=rightNode.down;

            rightNode.down.up=rightNode.up;

        }

        maxLevel--;
    }

    public void printList(){
        Node node=head;

        while(node.down!=null){
            node=node.down;
        }

        while(node.right.data!=Integer.MAX_VALUE){
            System.out.println(node.right.data+" ");
            node=node.right;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();
        skipList.insert(50);
        skipList.insert(15);
        skipList.insert(13);
        skipList.insert(20);
        skipList.insert(100);
        skipList.insert(75);
        skipList.insert(99);
        skipList.insert(76);
        skipList.insert(83);
        skipList.insert(65);

        skipList.printList();

        skipList.search(50);
        skipList.remove(50);
        skipList.search(50);


    }
}

